package E_2024;

import java.util.Arrays;

/*
题目描述
    工作安排
    小明每周上班都会拿到自己的工作清单，工作清单内包含n项工作，每项工作都有对应的耗时时长(单位h)和报酬，
    工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

输入描述
    输入的第一行为两个正整数T，n。
    T代表工作时长(单位h，0<T<100000)，n代表工作数量(1 < n< 3000)。
    接下来是n行，每行包含两个整数t，w。
    t代表该项工作消耗的时长(单位h，t>0)，w代表该项工作的报酬。
输出描述
    输出小明指定工作时长内工作可获得的最大报酬。
示例一
    输入
    40 3
    20 10
    20 20
    20 5
    输出
    30
 */
public class E_100_48 {
    public static void main(String[] args) {
        System.out.println(ans(40,3 ,new int[][]{{5,10},{20,20},{20,5}}));
        System.out.println(ans(40,3 ,new int[][]{{5,10},{20,20},{10,5}}));
        System.out.println(ans(40,3 ,new int[][]{{5,10},{20,5},{20,5}}));
        System.out.println(ans(40,3 ,new int[][]{{20,10},{20,20},{20,5}}));
    }
    // 背包问题，使用动态规划
    public static int ans(int time, int n, int[][] works){
        int[][] ans = new int[n+1][time+1];
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= time; k++) {
                // 通过比较完成当前工作获得的报酬与不完成当前工作（即只完成上一份工作）的报酬做比较，取大值，代表当前时间和任务数量下能够获得的最大价值
                if (k >= works[i-1][0])
                    ans[i][k] = Math.max(ans[i-1][k-works[i-1][0]] + works[i-1][1],ans[i-1][k]);
                else
                    ans[i][k] = ans[i][k-1];
            }
        }
        for (int[] an : ans) {
            System.out.println(Arrays.toString(an));
        }
        return ans[n][time];
    }
}
